#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <map>

using namespace std;
// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
		int left = 0;
		int right = 0;
		int max = 0;
		unordered_set<char> s1;
		while(right < s.size()){
			if(s1.find(s[right]) != s1.end()){
				// 代表找到
				// 左指针移动一次
				s1.erase(s[left]);
				left++;
				continue;
			}
			s1.insert(s[right]);
			int tmpSize = s1.size();
			if(tmpSize > max){
				max = tmpSize;
			}
			// 右指针移动一次
			right++;
		}

		return max;
    }
	
	// map解法
	int lengthOfLongestSubstring1(string s) {
		int left = 0;
		int right = 0;
		int max = 0;
		map<char,int> m1;

		while(right < s.size()){
			if(m1.find(s[right]) != m1.end()){
				// 代表找到
				// 左指针移动一次
				int tmpLeft = m1.at(s[right]) + 1;
				if(tmpLeft > left){
					left = tmpLeft;
				}
				
				// 更新重复元素的最新位置
				m1[s[right]] = right;
				cout << "right pos: " << m1.at(s[right]) << ", right val:" << s[right] << endl;
			}else{
				// 插入新的元素键值对
				m1.insert(pair<char,int>(s[right],right));
			}
			
			cout << "left pos: " << m1.at(s[left]) << ", left val:" << s[left] << endl;
			int len = right-left+1;
			if(len > max){
				max = len;
				cout << "max:" << max << endl;
			}
			// 右指针移动一次
			right++;
		}

		return max;
    }
	
	
	// 正宗的滚筒解法
	int lengthOfLongestSubstring2(string s) {
		unordered_set<char> s1;
		int left = 0;
		int max = 0;
		for(int i = 0; i < s.size(); i++){
			while(s1.find(s[i]) != s1.end()){
				// 找到记录
				s1.erase(s[left]);
				left++;
			}
			s1.insert(s[i]);
			// cout << "left:" << left << " , i: " << i << endl;
			if((i-left+1)>max){
				max = i-left+1;
			}
		}
		return max;
	}
};

int main(){
	string s = "pwwkew";
	// string s = "uqinntq";
	// string s = "abcabcbb";
	
	// string s = "bbbbb";
	// string s = "aab";
	// string s = "dvdf";
	
	
	Solution so;
	int len = so.lengthOfLongestSubstring2(s);
	
	cout << len << endl;
	return 0;
}

/*
1.
a
ab 
abc 

2.
b 
bc 
bca

3.
c 
ca 
cab 

4.
a 
ab 
abc 

5.
b 
bc 

6.
c 
cb 

7.
b 

8.
b 


*/